We present a novel idea to compute square roots over finite fields, withoutbeing given any quadratic nonresidue, and without assuming any unprovenhypothesis. The algorithm is deterministic and the proof is elementary. In somecases, the square root algorithm runs in $\tilde{O}(\log^2 q)$ bit operationsover finite fields with $q$ elements. As an application, we construct adeterministic primality proving algorithm, which runs in $\tilde{O}(\log^3 N)$for some integers $N$.
展开▼
